package com.xgb.edu.List;

public class LinkedList<E> {
	
	transient int size = 0;
	
	transient Node<E> first;
	
	transient Node<E> last;
	
	public LinkedList(){
		
	}
	
	private void linkFirst(E e){
		final Node<E> f = first;
		final Node<E> newNode = new Node<>(null , e ,f);
		first = newNode;
		if(f == null)
			last = newNode;
		else
			f.prev = newNode;
		size++;
	}
	
	void linkLast(E e){
		final Node<E> l = last;
		final Node<E> newNode = new Node<>(l , e ,null);
		last = newNode;
		if(l == null)
			first = newNode;
		else
			l.next = newNode;
		size++;
	}
	
	
	/**
	 * 解除绑定链表头部
	 * @param f 
	 * @return
	 */
	private E unLinkFirst(Node<E> f) {
		final E element = f.item; //当前元素
		final Node<E> next = f.next; //设置next为f.next
		f.item = null; //清除当前节点的数据
		f.next = null; //设置下一个节点为空
		first = next; //设置链表表头为next节点
		if(next == null) //如果头结点的下一个 节点为空，表示没有下一个元素，那么需要设置链表尾部为空，否则表示还有下一个节点，那么需要设置下一个节点的前驱节点为空（因为first已经被删除了）
			last = null;
		else
			next.prev = null;
		size--;
		return element;
	}
	
	/**
	 * 解除绑定链表尾部
	 * @param l
	 * @return
	 */
	private E unLinkLast(Node<E> l) {
		final E element = l.item; //当前元素element
		final Node<E> prev = l.prev; //设置prev节点为l.prev
		l.item = null; //清空item数据
		l.prev = null; //清空l的前驱节点
		last = null; //设置last为空
		if(prev == null) //如果prev节点为空，表示没有前驱节点需要设置frist为空，否则表示还有前驱节点，那么需要设置前节点的next节点为空（因为当前的last已经被删除了）
			first = null;
		else 
			last.next = null;
		size--;
		return element;
	}
	
	
	/**
	 * 获取表头元素
	 * @return
	 */
	public E getFirst() {
		final Node<E> f = first;
		if(f == null)
			throw new RuntimeException("No the first itemm...");
		return f.item;
		
	}
	
	/**
	 * 获取链尾元素
	 * @return
	 */
	public E getLast() {
		final Node<E> l = last;
		if(l == null)
			throw new RuntimeException("No the last itemm...");
		return l.item;
	}
	
	
	public E removeFirst() {
		final Node<E> f = first;
		if(f == null)
			throw new RuntimeException("No the first item...");
		return unLinkFirst(f);
	}
	
	public E removeLast() {
		final Node<E> l = last;
		if(l == null)
			throw new RuntimeException("No the last item...");
		return unLinkLast(l);
	}
	
	public void addFirst(E e) {
		linkFirst(e);
	}
	
	public void addLast(E e) {
		linkLast(e);
	}
	
	public boolean contains(Object o) {
		return indexOf(o) != -1;
	}
	
	/**
	 * 查找某个元素的第一次出现的索引
	 * @param o
	 * @return 返回-1 表示该元素不被链表包含
	 */
	public int indexOf(Object o) {
		int index = 0; // 索引
		if(o == null) { //如果查找的o为空，需要循环遍历链表，如果链表的某个节点item元素值为空，返回找到的索引
			for(Node<E> x = first ; x != null ;x = x.next) {
				if(x.item == null)
					return index;
				index++;
			}
		}else { // 如果查找的o不为空，则需要循环遍历链表，一一对比链表的元素节点是否和o相等（equals），返回找到的索引位置 
			for(Node<E> x = first;x != null ;x = x.next) {
				if(o.equals(x))
					return index;
				index++;
			}
		}
		return -1;
	}
	
	public Node<E> add(Node<E> node){
		
		return null;
	}
	
	
}
